//! 数据结构工具

use std::collections::VecDeque;
use std::fmt::Debug;

/// 循环缓冲区实现
#[derive(Debug, Clone)]
pub struct CircularBuffer<T> {
    buffer: VecDeque<T>,
    capacity: usize,
}

impl<T> CircularBuffer<T> {
    /// 创建一个新的循环缓冲区
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// assert_eq!(buffer.capacity(), 3);
    /// assert_eq!(buffer.len(), 0);
    /// ```
    pub fn new(capacity: usize) -> Self {
        CircularBuffer {
            buffer: VecDeque::with_capacity(capacity),
            capacity,
        }
    }

    /// 获取缓冲区容量
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let buffer: CircularBuffer<i32> = CircularBuffer::new(5);
    /// assert_eq!(buffer.capacity(), 5);
    /// ```
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// 获取缓冲区当前长度
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// assert_eq!(buffer.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.buffer.len()
    }

    /// 检查缓冲区是否为空
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// assert_eq!(buffer.is_empty(), true);
    /// buffer.push(1);
    /// assert_eq!(buffer.is_empty(), false);
    /// ```
    pub fn is_empty(&self) -> bool {
        self.buffer.is_empty()
    }

    /// 向缓冲区添加元素
    /// 如果缓冲区已满，会移除最旧的元素
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// buffer.push(3);
    /// buffer.push(4); // 这会移除最旧的元素 1
    /// assert_eq!(buffer.to_vec(), vec![2, 3, 4]);
    /// ```
    pub fn push(&mut self, item: T) {
        if self.buffer.len() >= self.capacity {
            self.buffer.pop_front();
        }
        self.buffer.push_back(item);
    }

    /// 从缓冲区取出最旧的元素
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// buffer.push(3);
    /// 
    /// assert_eq!(buffer.pop(), Some(1));
    /// assert_eq!(buffer.pop(), Some(2));
    /// assert_eq!(buffer.pop(), Some(3));
    /// assert_eq!(buffer.pop(), None);
    /// ```
    pub fn pop(&mut self) -> Option<T> {
        self.buffer.pop_front()
    }

    /// 查看缓冲区中最旧的元素但不移除它
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// 
    /// assert_eq!(buffer.front(), Some(&1));
    /// assert_eq!(buffer.len(), 2); // 长度没有变化
    /// ```
    pub fn front(&self) -> Option<&T> {
        self.buffer.front()
    }

    /// 查看缓冲区中最新的元素但不移除它
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// 
    /// assert_eq!(buffer.back(), Some(&2));
    /// assert_eq!(buffer.len(), 2); // 长度没有变化
    /// ```
    pub fn back(&self) -> Option<&T> {
        self.buffer.back()
    }

    /// 将缓冲区转换为Vec
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::CircularBuffer;
    /// 
    /// let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
    /// buffer.push(1);
    /// buffer.push(2);
    /// buffer.push(3);
    /// 
    /// assert_eq!(buffer.to_vec(), vec![1, 2, 3]);
    /// ```
    pub fn to_vec(&self) -> Vec<T>
    where
        T: Clone,
    {
        self.buffer.iter().cloned().collect()
    }
}

/// 二叉树节点
#[derive(Debug, Clone)]
pub struct TreeNode<T> {
    pub value: T,
    pub left: Option<Box<TreeNode<T>>>,
    pub right: Option<Box<TreeNode<T>>>,
}

impl<T> TreeNode<T> {
    /// 创建一个新的树节点
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::TreeNode;
    /// 
    /// let node = TreeNode::new(10);
    /// assert_eq!(node.value, 10);
    /// assert!(node.left.is_none());
    /// assert!(node.right.is_none());
    /// ```
    pub fn new(value: T) -> Self {
        TreeNode {
            value,
            left: None,
            right: None,
        }
    }

    /// 添加左子节点
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::TreeNode;
    /// 
    /// let mut root = TreeNode::new(10);
    /// root.add_left(5);
    /// assert!(root.left.is_some());
    /// assert_eq!(root.left.unwrap().value, 5);
    /// ```
    pub fn add_left(&mut self, value: T) {
        self.left = Some(Box::new(TreeNode::new(value)));
    }

    /// 添加右子节点
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::TreeNode;
    /// 
    /// let mut root = TreeNode::new(10);
    /// root.add_right(15);
    /// assert!(root.right.is_some());
    /// assert_eq!(root.right.unwrap().value, 15);
    /// ```
    pub fn add_right(&mut self, value: T) {
        self.right = Some(Box::new(TreeNode::new(value)));
    }
}

/// LRU (Least Recently Used) 缓存实现
#[derive(Debug, Clone)]
pub struct LRUCache<K, V> {
    map: std::collections::HashMap<K, (V, usize)>,
    list: std::collections::LinkedList<K>,
    capacity: usize,
    timestamp: usize,
}

impl<K, V> LRUCache<K, V>
where
    K: Clone + std::hash::Hash + Eq + Debug,
    V: Clone + Debug,
{
    /// 创建一个新的LRU缓存
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let cache: LRUCache<String, i32> = LRUCache::new(3);
    /// assert_eq!(cache.capacity(), 3);
    /// assert_eq!(cache.len(), 0);
    /// ```
    pub fn new(capacity: usize) -> Self {
        LRUCache {
            map: std::collections::HashMap::new(),
            list: std::collections::LinkedList::new(),
            capacity,
            timestamp: 0,
        }
    }

    /// 获取缓存容量
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let cache: LRUCache<String, i32> = LRUCache::new(5);
    /// assert_eq!(cache.capacity(), 5);
    /// ```
    pub fn capacity(&self) -> usize {
        self.capacity
    }

    /// 获取缓存当前长度
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let mut cache: LRUCache<String, i32> = LRUCache::new(3);
    /// cache.put("key1".to_string(), 1);
    /// cache.put("key2".to_string(), 2);
    /// assert_eq!(cache.len(), 2);
    /// ```
    pub fn len(&self) -> usize {
        self.map.len()
    }

    /// 检查缓存是否为空
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let mut cache: LRUCache<String, i32> = LRUCache::new(3);
    /// assert_eq!(cache.is_empty(), true);
    /// cache.put("key1".to_string(), 1);
    /// assert_eq!(cache.is_empty(), false);
    /// ```
    pub fn is_empty(&self) -> bool {
        self.map.is_empty()
    }

    /// 向缓存中添加键值对
    /// 如果缓存已满，会移除最近最少使用的元素
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let mut cache: LRUCache<String, i32> = LRUCache::new(2);
    /// cache.put("key1".to_string(), 1);
    /// cache.put("key2".to_string(), 2);
    /// cache.put("key3".to_string(), 3); // 这会移除 "key1"
    /// assert_eq!(cache.get(&"key1".to_string()), None);
    /// assert_eq!(cache.get(&"key2".to_string()), Some(&2));
    /// assert_eq!(cache.get(&"key3".to_string()), Some(&3));
    /// ```
    pub fn put(&mut self, key: K, value: V) {
        self.timestamp += 1;
        
        if self.map.len() >= self.capacity && !self.map.contains_key(&key) {
            // 移除最近最少使用的元素
            if let Some(oldest_key) = self.list.pop_front() {
                self.map.remove(&oldest_key);
            }
        } else {
            // 如果键已存在，先从链表中移除
            self.list = self.list.iter()
                .filter(|&k| k != &key)
                .cloned()
                .collect();
        }
        
        // 更新map
        self.map.insert(key.clone(), (value, self.timestamp));
        // 将键添加到链表末尾（表示最近使用）
        self.list.push_back(key);
    }

    /// 从缓存中获取值
    /// 
    /// # 示例
    /// 
    /// ```
    /// use rust_utils::data_structure::LRUCache;
    /// 
    /// let mut cache: LRUCache<String, i32> = LRUCache::new(3);
    /// cache.put("key1".to_string(), 1);
    /// cache.put("key2".to_string(), 2);
    /// 
    /// assert_eq!(cache.get(&"key1".to_string()), Some(&1));
    /// assert_eq!(cache.get(&"key3".to_string()), None);
    /// ```
    pub fn get(&mut self, key: &K) -> Option<&V> {
        self.timestamp += 1;
        
        if let Some((value, _)) = self.map.get_mut(key) {
            // 更新时间戳
            *value = value.clone();
            // 将键移动到链表末尾（表示最近使用）
            self.list = self.list.iter()
                .filter(|&k| k != key)
                .cloned()
                .collect();
            self.list.push_back(key.clone());
            Some(value)
        } else {
            None
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_circular_buffer() {
        let mut buffer: CircularBuffer<i32> = CircularBuffer::new(3);
        
        assert_eq!(buffer.capacity(), 3);
        assert_eq!(buffer.len(), 0);
        assert!(buffer.is_empty());
        
        buffer.push(1);
        buffer.push(2);
        buffer.push(3);
        
        assert_eq!(buffer.len(), 3);
        assert!(!buffer.is_empty());
        assert_eq!(buffer.front(), Some(&1));
        assert_eq!(buffer.back(), Some(&3));
        
        buffer.push(4); // 这应该移除最旧的元素 1
        assert_eq!(buffer.len(), 3);
        assert_eq!(buffer.to_vec(), vec![2, 3, 4]);
        
        assert_eq!(buffer.pop(), Some(2));
        assert_eq!(buffer.pop(), Some(3));
        assert_eq!(buffer.pop(), Some(4));
        assert_eq!(buffer.pop(), None);
    }

    #[test]
    fn test_tree_node() {
        let mut root = TreeNode::new(10);
        root.add_left(5);
        root.add_right(15);
        
        assert_eq!(root.value, 10);
        assert!(root.left.is_some());
        assert!(root.right.is_some());
        assert_eq!(root.left.unwrap().value, 5);
        assert_eq!(root.right.unwrap().value, 15);
    }

    #[test]
    fn test_lru_cache() {
        let mut cache: LRUCache<String, i32> = LRUCache::new(2);
        
        assert_eq!(cache.capacity(), 2);
        assert_eq!(cache.len(), 0);
        assert!(cache.is_empty());
        
        cache.put("key1".to_string(), 1);
        cache.put("key2".to_string(), 2);
        
        assert_eq!(cache.len(), 2);
        assert!(!cache.is_empty());
        assert_eq!(cache.get(&"key1".to_string()), Some(&1));
        assert_eq!(cache.get(&"key2".to_string()), Some(&2));
        
        cache.put("key3".to_string(), 3); // 这应该移除 "key1"
        
        assert_eq!(cache.len(), 2);
        assert_eq!(cache.get(&"key1".to_string()), None);
        assert_eq!(cache.get(&"key2".to_string()), Some(&2));
        assert_eq!(cache.get(&"key3".to_string()), Some(&3));
    }
}